package com.xyhuo.leetcode.december;

import java.util.ArrayList;
import java.util.List;

/**
 * 到达首都最小的油耗
 * https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital/
 *
 * @desc 没做出来，看的题解
 * @time 2023/12/5
 */
public class MinimumFuelCost {

//    public static void main(String[] args) {
//        MinimumFuelCost minimumFuelCost = new MinimumFuelCost();
//        int[][] roads = {{0, 1}, {0, 2}, {0, 3}};
//
//        minimumFuelCost.minimumFuelCost(roads, 5);
//    }

    private int res = 0;

    private int seats;

    public long minimumFuelCost(int[][] roads, int seats) {
        int n = roads.length + 1;
        List<Integer>[] dp = new List[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new ArrayList<>();
        }
        this.seats = seats;
        for (int[] road : roads) {
            dp[road[0]].add(road[1]);
            dp[road[1]].add(road[0]);
        }
        dfs(0, -1, dp);
        return res;
    }

    private int dfs(int index, int fa, List<Integer>[] dp) {
        int peopleSum = 1;
        for (Integer nextIndex : dp[index]) {
            if (nextIndex != fa) {
                int people = dfs(nextIndex, index, dp);
                peopleSum += people;
                res += (people + seats - 1) / seats;
            }
        }
        return peopleSum;
    }
}
